//
// Created by wormtql on 2020/11/8.
//

#include <map>
#include <string>
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <set>
#include <cmath>

#define INF 0x3f3f3f3f
//#define REMOTE

using namespace std;

struct Edge {
    int to;
    int from;
    int next;
};

#ifdef REMOTE
int dis_cache[11000][11000] = { 0 };
#else
int dis_cache[1000][1000] = { 0 };
#endif
map<string, int> function_name_to_index;

// 图
#ifdef REMOTE
Edge edges[5000000];
int edge_count = 0;
int head[600000];
int node_count = 0;
int dis[600000];
int vis[600000];
int parent[600000];
#else
Edge edges[2000000];
int edge_count = 0;
int head[500000];
int node_count = 0;
int dis[500000];
int vis[500000];
int parent[500000];
#endif
map<string, int> name2id;
map<int, string> id2name;

int trace_count = 0;
vector<int> traces[6000];

// trace总node数
int trace_node_count = 0;
int trace_found_node_count = 0;

// 最终calltrace文件
ofstream final_tr;
bool need_final_tr = true;

int mat_start = 0;
int mat_end = 10000;

//set<string> black_list = {
//        "__stack_chk_fail"
//};

void init() {
    memset(edges, -1, sizeof(edges));
    memset(head, -1, sizeof(head));
    edge_count = 0;
    node_count = 0;
    name2id.clear();

    trace_node_count = 0;
    trace_found_node_count = 0;
}

bool parseLine(const char * line, char * from, char * to) {
    int i = 0;
    bool flag = false;
    bool isFrom = true;

    int a = 0;
    int b = 0;

    while (line[i] != '\0') {
        if (line[i] == '\"') {
            if (!flag) {
                flag = true;
            } else {
                if (!isFrom) {
                    break;
                }
                flag = false;
                isFrom = false;
            }
            i++;
            continue;
        }

        if (flag) {
            if (isFrom) {
                from[a] = line[i];
                a++;
            } else {
                to[b] = line[i];
                b++;
            }
        }
        i++;
    }

    if (a == 0 || b == 0) {
        return false;
    }

    from[a] = 0;
    to[b] = 0;

    return true;
}

//bool parse_trace_line(const char * line, char * version, char * commit_id, vector<string> & trace) {
//    int i = 0;
//    int state = 0;
//
//    int _v = 0;
//    int _c = 0;
//    char _trace[100] = { 0 };
//    int _t = 0;
//    while(line[i]) {
//        if (state == 0) {
//            if (line[i] == '\t' || line[i] == ' ') {
//                version[_v] = 0;
//                state = 1;
//            } else {
//                version[_v++] = line[i];
//                i++;
//            }
//        } else if (state == 1) {
//            if (line[i] == '\t' || line[i] == ' ') {
//                i++;
//            } else {
//                state = 2;
//            }
//        } else if (state == 2) {
//            if (line[i] == '\t' || line[i] == ' ') {
//                commit_id[_c] = 0;
//                state = 3;
//            } else {
//                commit_id[_c++] = line[i];
//                i++;
//            }
//        } else if (state == 3) {
//            if (line[i] == '\t' || line[i] == ' ') {
//                i++;
//            } else {
//                state = 4;
//            }
//        } else if (state == 4) {
//            if (line[i] == '\'') {
//                state = 5;
//                i++;
//            } else if (line[i] == ']') {
//                state = 6;
//                i++;
//            } else {
//                i++;
//            }
//        } else if (state == 5) {
//            if (line[i] == '\'') {
//                _trace[_t] = 0;
//                _t = 0;
//                string s(_trace);
//                trace.push_back(s);
//                state = 4;
//                i++;
//            } else {
//                _trace[_t++] = line[i];
//                i++;
//            }
//        } else if (state == 6) {
//            i++;
//        }
//    }
//
//    return true;
//}

void parse_csv_line(char * line, vector<string> & data) {
    int state = 0;
    char buf[1000] = { 0 };
    int l = 0;

    int i = 0;
    while (line[i]) {
        if (state == 0) {
            if (line[i] == ',') {
                state = 1;
            } else {
                buf[l++] = line[i];
                i++;
            }
        } else if (state == 1) {
            buf[l] = 0;
            l = 0;
            data.push_back(string(buf));
            i++;
            state = 0;
        }
    }
    if (l != 0) {
        buf[l] = 0;
        data.emplace_back(buf);
    }
}

bool load_traces(char * filename, int limit) {
    ifstream file(filename);
    if (!file.is_open()) {
        return false;
    }

    char buf[10000];
    while(file.getline(buf, 10000) && trace_count < limit) {
//        char version[100];
//        char commit_id[100];
        vector<string> ts;
//        parse_trace_line(buf, version, commit_id, ts);
        parse_csv_line(buf, ts);

        for (const string & s: ts) {
//            printf("%s\n", s.c_str());
            if (name2id.find(s) != name2id.end()) {
                trace_found_node_count++;
                traces[trace_count].push_back(name2id[s]);
                if (need_final_tr) {
                    final_tr << s << ",";
                }
            }
            trace_node_count++;
        }
        if (need_final_tr) {
            final_tr << endl;
        }

        trace_count++;
    }

    return true;
}

int register_node(char * name) {
    string temp(name);
    if (name2id.find(temp) == name2id.end()) {
        name2id[name] = node_count;
        id2name[node_count] = name;
        node_count++;
        return node_count - 1;
    } else {
        return name2id[temp];
    }
}

void add(int from, int to) {
    edges[edge_count].from = from;
    edges[edge_count].to = to;
    edges[edge_count].next = head[from];
    head[from] = edge_count;
    edge_count++;
}

//bool check(char * str) {
//    if (black_list.find(string(str)) == black_list.end()) {
//        return true;
//    }
//
//    return false;
//}

bool load_graph(char * filename) {
    ifstream file(filename);

    if (!file.is_open()) {
        return false;
    }

    char line[1000] = { 0 };
    while(file.getline(line, 1000)) {
        char from[100] = { 0 };
        char to[100] = { 0 };

        bool ret = parseLine(line, from, to);
        if (!ret) {
            printf("aaa\n");
            continue;
        }
//        if (!check(from) || !check(to)) {
//            continue;
//        }

        int from_id = register_node(from);
        int to_id = register_node(to);
        add(from_id, to_id);
//        add(to_id, from_id);
    }

    return true;
}

int sp(const vector<int> & a, const vector<int> & b) {
    int edge_count_bk = edge_count;

    for (int i: a) {
        add(node_count, i);
    }
    for (int i: b) {
        add(i, node_count + 1);
    }

    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(parent, -1, sizeof(parent));

    queue<int> q;
    q.push(node_count);
    dis[node_count] = 0;
    vis[node_count] = 1;

    bool flag = false;
    int ans = 0;
    while(!q.empty()) {
        int p = q.front();
        q.pop();

        for (int e = head[p]; e != -1; e = edges[e].next) {
            int to = edges[e].to;
            if (to == node_count + 1) {
                flag = true;
                parent[to] = p;
                ans = dis[p] + 1 - 2;
                break;
            }

            if (!vis[to]) {
                q.push(to);
                vis[to] = 1;
                dis[to] = dis[p] + 1;
                parent[to] = p;
            }
        }
        if (flag) {
            break;
        }
    }

    edge_count = edge_count_bk;
    head[node_count] = -1;
    head[node_count + 1] = -1;
    for (int i: b) {
        head[i] = edges[head[i]].next;
    }

    return flag ? ans : INF;
}

void sp_single(int a) {
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(parent, -1, sizeof(parent));

    queue<int> q;
    q.push(a);
    dis[a] = 0;
    vis[a] = 1;

    while(!q.empty()) {
        int p = q.front();
        q.pop();

        for (int e = head[p]; e != -1; e = edges[e].next) {
            int to = edges[e].to;

            if (!vis[to]) {
                q.push(to);
                vis[to] = 1;
                dis[to] = dis[p] + 1;
                parent[to] = p;
            }
        }
    }
}

char buf[150000] = { 0 };
void load_dis_cache(char * filename, char * function_list, int limit) {
    ifstream file(filename);
    ifstream fl(function_list);

//    char buf[150000] = { 0 };

    int it = 0;
    while (fl.getline(buf, 150000) && it < limit) {
        function_name_to_index[buf] = it;
        it++;
    }

    it = 0;
    while (file.getline(buf, 150000) && it < limit) {
        vector<string> temp;
        parse_csv_line(buf, temp);

        for (int i = 0; i < temp.size() && i < limit; i++) {
            int d = atoi(temp[i].c_str());
            dis_cache[it][i] = d;
        }

        it++;
    }

    file.close();
    fl.close();
}

void print_sp() {
    for(int e = parent[node_count + 1]; e != -1; e = parent[e]) {
        if (e == node_count) {
            break;
        }
        cout << id2name[e] << endl;
    }
}

int get_cached_dis(int a, int b) {
    if (id2name.find(a) == id2name.end()) {
        return INF;
    }
    if (id2name.find(b) == id2name.end()) {
        return INF;
    }
    if (function_name_to_index.find(id2name[a]) == function_name_to_index.end()) {
        return INF;
    }
    if (function_name_to_index.find(id2name[b]) == function_name_to_index.end()) {
        return INF;
    }
    int index_a = function_name_to_index[id2name[a]];
    int index_b = function_name_to_index[id2name[b]];

    return dis_cache[index_a][index_b];
}

// app <graph.dot> <calltrace.txt>
int main(int argc, char * argv[]) {
#ifdef REMOTE
    printf("running remotely\n");
#endif
    if (argc < 8) {
        printf("distance between two representative node\n\n");
        printf("app <graph.dot> <calltrace.csv> <start> <end+1> <dis_cache.csv> <function_list.txt> <outfile>\n\n");
        printf("graph.dot:          call graph\n");
        printf("calltrace.csv:      call trace\n");
        printf("start, end:         ...\n");
        printf("dis_cache.csv:      cached distance, use binary \'dis_cache\' to generate\n");
        printf("function_list.txt:  generate by \'dis_cache\'\n");
        printf("outfile:            output matrix\n");
        return 0;
    }

    init();


    // start end
    mat_start = atoi(argv[3]);
    mat_end = atoi(argv[4]);

    // load graph
    bool ret = load_graph(argv[1]);
    if (!ret) {
        printf("unable to open file \"%s\"\n", argv[1]);
    }
    printf("graph loaded\n");
    printf("node count: %d\n", node_count);
    printf("edge count: %d\n", edge_count);

    // load traces
    load_traces(argv[2], 10000);
    printf("\ntraces loaded\n");
    printf("trace count: %d\n", trace_count);
    printf("trace node count: %d\n", trace_node_count);
    printf("found trace node count: %d\n", trace_found_node_count);
    printf("rate: %.6lf\n", 1.0 * trace_found_node_count / trace_node_count);

    // load distance cache
#ifdef REMOTE
    load_dis_cache(argv[5], argv[6], 1000000);
#else
    load_dis_cache(argv[5], argv[6], 100);
#endif
    printf("\ndis cache loaded\n\n");

    mat_end = min(mat_end, trace_count);

    ofstream out_file(argv[7]);

    for (int i = mat_start; i < mat_end; i++) {
        if (traces[i].size() == 0) {
            for (int j = 0; j < trace_count; j++) {
                out_file << INF;
                if (j != trace_count - 1) {
                    out_file << ",";
                }
            }
        } else {
//            sp_single(traces[i][0]);
//            for (int j = 0; j < trace_count; j++) {
//                int d = 0;
//                if (traces[j].size() == 0) {
//                    d = INF;
//                } else {
//                    d = dis[traces[j][0]];
//                }
//                out_file << d;
//                if (j != trace_count - 1) {
//                    out_file << ",";
//                }
//            }
            for (int j = 0; j < trace_count; j++) {
                int d = 0;
                if (traces[j].size() == 0) {
                    d = INF;
                } else {
                    d = get_cached_dis(traces[i][0], traces[j][0]);
                }
                out_file << d;
                if (j != trace_count - 1) {
                    out_file << ",";
                }
            }
        }

        printf("%.6lf%%\n", (i + 1.0 - mat_start) / (mat_end - mat_start) * 100);
        out_file << endl;
    }

//    for (int i = 0; i < trace_count; i++) {
//        int x = sp(traces[0], traces[i]);
//        printf("%d\n", x);
//    }
//    printf("666\n");

//    printf("%d\n", sp(traces[0], traces[100]));
//    print_sp();

    out_file.close();

    return 0;
}